perm filename OVERV[AM,DBL]1 blob
sn#373534 filedate 1978-08-14 generic text, type T, neo UTF8
00100 .NSECP(Overview)
00200
00300 .SKIP 4
00400
00500 .OVERV: SECNUM ;
00600
00700 .QQ
00800
00900 Indeed, you can build a machine to draw demonstrative conclusions for you,
01000 but I think you can never build a machine that will draw plausible inferences.
01100
01200 -- Polya
01300
01400 .ESS
01500
01600 .SKIP 4
01700
00100 .SSEC(Abstract of this Thesis)
00200
00300 A program, called "AM", is described which models one aspect of
00400 elementary mathematics research: developing new concepts under the
00500 guidance of a large body of heuristic rules. "Mathematics" is
00600 considered as a type of intelligent behavior, not merely
00700 as a finished
00800 product.
00900
01000 The local heuristics communicate via an agenda mechanism, a global
01100 list of tasks for the system to perform and reasons why each task is
01200 plausible. A single task might direct AM to define a new concept, or
01300 to explore some facet of an existing concept, or to examine some
01400 empirical data for regularities, etc. Repeatedly, the program
01500 selects from the agenda the task having the best supporting reasons,
01600 and then executes it.
01700
01800 Each concept is an active, structured knowledge module. A hundred
01900 very incomplete modules are initially provided, each one
02000 corresponding to an elementary set-theoretic concept (e.g., union).
02100 This provides a definite but immense "space" which AM begins to
02200 explore, guided by a corpus of 250 heuristic rules. AM extends its
02300 knowledge base, ultimately rediscovering hundreds of common concepts
02400 (e.g., numbers) and theorems (e.g., unique factorization).
02500
00100 .SSECP(Five-page Summary of the Project)
00200
00300 Scientists often face the difficult task of formulating nontrivial
00400 research problems which are solvable. In any given branch of
00500 science, it is usually easier to tackle a specific given problem than
00600 to propose interesting yet managable new questions to investigate.
00700 For example, contrast ⊗4solving⊗* the Missionaries and Cannibals
00800 problem with the more ill-defined reasoning which led to
00900 ⊗4inventing⊗* it.
01000
01100 This thesis is concerned with creative theory formation in
01200 mathematics: how to propose interesting new concepts and plausible
01300 hypotheses connecting them. The experimental vehicle of my research
01400 is a computer program called ⊗2AM⊗*$$ The original meaning of this
01500 mnemonic has been abandoned. As Exodus states: I ↓_AM_↓ that I
01600 ↓_AM_↓. $
01700 Initially, AM is
01800 given the definitions of 115 simple set-theoretic concepts (like
01900 "Delete", "Equality"). Each concept is represented internally as a
02000 data structure with a couple dozen slots or facets (like
02100 "Definition", "Examples", "Worth"). Initially, most facets of most
02200 concepts are blank, and AM uses a collection of 250 heuristics --
02300 plausible rules of thumb -- for guidance, as it tries to fill in
02400 those blanks. Some heuristics are used to select which specific facet
02500 of which specific concept to explore next, while others are used to
02600 actually find some appropriate information about the chosen facet.
02700 Other rules prompt AM to notice simple relationships between known
02800 concepts, to define promising new concepts to investigate, and to
02900 estimate how interesting each concept is.
03000
00100 . SSSEC(Detour: Analysis of a discovery)
00200
00300 Before discussing how to ⊗4synthesize⊗* a new theory, consider
00400 briefly how to ⊗4analyze⊗* one, how to construct a plausible chain of
00500 reasoning which terminates in a given discovery. One can do this by
00600 working backwards, by reducing the creative act to simpler and
00700 simpler creative acts. For example, consider the concept of prime
00800 numbers. How might one be led to define such a notion? Notice the
00900 following plausible strategy:
01000
01100 .ONCE INDENT 9,9,9 SELECT 6
01200
01300 "If f is a function which transforms elements of A into elements of
01400 B, and B is ordered, then consider just those members of A which are
01500 transformed into ⊗4extremal⊗* elements of B. This set is an
01600 interesting subset of A."
01700
01800 When f(x) means "divisors of x", and the ordering is "by length",
01900 this heuristic says to consider those numbers which have a minimal$$
02000 The other extreme, numbers with a MAXIMAL number of factors, was also
02100 proposed by AM as worth investigating. This led AM to many
02200 interesting questions. See Appendix {[2]MAXDIV⎇. $ number of factors
02300 -- that is, the primes. So this rule actually ⊗4reduces⊗* our task
02400 from "proposing the concept of prime numbers" to the more elementary
02500 problems of "discovering ordering-by-length" and "inventing
02600 divisors-of".
02700
02800 But suppose we know this general rule: ⊗6"If f is an interesting
02900 function, consider its inverse."⊗* It reduces the task of discovering
03000 divisors-of to the simpler task of discovering multiplication$$ Plus
03100 noticing that multiplication is associative and commutative. $.
03200 Eventually, this task reduces to the discovery of very basic notions,
03300 like substitution, set-union, and equality. To explain how a given
03400 researcher might have made a given discovery, such an analysis is
03500 continued until that inductive task is reduced to "discovering"
03600 notions which the researcher already knew, which were his conceptual
03700 primitives.
03800
00100 . SSSEC(What AM does: Syntheses of discoveries)
00200
00300 .QQ
00400
00500 This leads to the paradox that the more original a discovery the more obvious
00600 it seems afterwards.
00700 The creative act is not an act of creation in the sense of the Old Testament.
00800 It does not create something out of nothing; it uncovers, selects, re-shuffles,
00900 combines, synthesizes already existing facts, faculties, skills.
01000 The more familiar the parts, the more striking the new whole.
01100
01200 -- Koestler
01300
01400 .ESS
01500
01600 Suppose a large collection of these heuristic strategies has been
01700 assembled (e.g., by analyzing a great many discoveries, and writing
01800 down new heuristic rules whenever necessary). Instead of using them
01900 to ⊗4explain⊗* how a given idea might have evolved, one can imagine
02000 starting from a basic core of knowledge and "running" the heuristics
02100 to ⊗4generate⊗* new concepts. We're talking about reversing the
02200 process described in the last section: not how to ⊗4explain⊗*
02300 discoveries, but how to ⊗4make⊗* them.
02400
02500 Such syntheses are precisely what AM does. The program consists of a
02600 large corpus of primitive mathematical concepts, each with a few
02700 associated heuristics$$ Situation/action rules which function as
02800 local "plausible move generators". Some suggest tasks for the system
02900 to carry out, some suggest ways of satisfying a given task, etc. $.
03000 AM's activities all serve to expand AM itself, to enlarge upon a
03100 given body of mathematical knowledge. To cope with the enormity of
03200 the potential "search space" involved, AM uses its heuristics as
03300 judgmental criteria to guide development in the most promising
03400 direction. It appears that the process of inventing worthwhile new$$
03500 Typically, "new" means new to AM, not to Mankind; and "worthwhile"
03600 can only be judged in hindsight. $ concepts can be guided
03700 successfully using a collection of a few hundred such heuristics.
03800
03900 Each concept is represented as a frame-like data structure with 25
04000 different facets or slots. The types of facets include: ⊗6Examples,
04100 Definitions, Generalizations, Domain/Range, Analogies,
04200 Interestingness,⊗* and many others. Modular representation of
04300 concepts provides a convenient scheme for organizing the heuristics;
04400 for example, the following strategy fits into the ⊗4Examples⊗* facet
04500 of the ⊗4Predicate⊗* concept: ⊗6"If, empirically, 10 times as many
04600 elements ⊗4fail⊗* some predicate P, as ⊗4satisfy⊗* it, then some
04700 ⊗4generalization⊗* (weakened version) of P might be more interesting
04800 than P"⊗1. AM considers this suggestion after trying to fill in
04900 examples of each predicate$$ In fact, after AM attempts to find
05000 examples of SET-EQUALITY, so few are found that AM decides to
05100 generalize that predicate. The result is the creation of
05200 a new predicate which means
05300 "Has-the-same-length-as" -- i.e., a rudimentary precursor to natural
05400 numbers. $.
05500
05600 AM is initially given a collection of 115 core concepts, with only a
05700 few facets filled in for each. Its sole activity is to choose some
05800 facet of some concept, and fill in that particular slot. In so
05900 doing, new notions will often emerge. Uninteresting ones are
06000 forgotten, mildly interesting ones are kept as parts of one facet of
06100 one concept, and very interesting ones are granted full
06200 concept-module status. Each of these new modules has dozens of blank
06300 slots, hence the space of possible actions (blank facets to fill in)
06400 grows rapidly. The same heuristics are used both to suggest new
06500 directions for investigation, and to limit attention: both to sprout
06600 and to prune.
06700
00100 . SSSEC(Results)
00200
00300 The particular mathematical domains in which AM operates depend upon
00400 the choice of initial concepts. Currently, AM begins with nothing
00500 but a scanty knowledge of concepts which Piaget might describe as
00600 ⊗4prenumerical⊗*: Sets, substitution, operations, equality, and so
00700 on. In particular, AM is not told anything about proof,
00800 single-valued functions, or numbers.
00900
01000 From this primitive basis, AM quickly discovered$$ "Discovering" a
01100 concept means that (1) AM recognized it as a distinguished entity
01200 (e.g., by formulating its definition) and also (2) AM decided it was
01300 worth investigating (either because of the interesting way it was
01400 formed, or because of surprising preliminary empirical results). $
01500 elementary numerical concepts (corresponding to those we refer to as
01600 natural numbers, multiplication, factors, and primes) and wandered
01700 around in the domain of elementary number theory. AM was not designed
01800 to ⊗4prove⊗* anything, but it did ⊗4conjecture⊗* many well-known
01900 relationships (e.g., the unique factorization theorem).
02000
02100 AM was not able to discover any "new-to-Mankind" mathematics purely
02200 on its own, but ⊗4has⊗* discovered several interesting notions
02300 hitherto unknown to the author. A couple bits of new mathematics have
02400 been ⊗4inspired⊗* by AM.⊗A2⊗* A synergetic AM--human combination can
02500 sometimes produce better research than either could alone.$$ This is
02600 supported by Gelernter's experiences with his geometry program: While
02700 lecturing about how it might prove a certain theorem about isosceles
02800 triangles, he came up with a new, cute proof. Similarly, Guard and
02900 Eastman noticed an intermediate result of their SAM resolution
03000 theorem prover, and wisely interpreted it as a nontrivial result in
03100 lattice theory (now known as SAM's lemma). $ Although most of the
03200 concepts AM proposed and developed were already very well known, AM
03300 defined some of them in novel ways (e.g., prime pairs were defined by
03400 restricting addition to primes; that is, for which primes p,q,r is it
03500 possible that p+q=r?$$ The answer is that either p or q must be 2,
03600 and that the other two primes are a prime pair -- i.e., they differ
03700 by two. $).
03800
03900 Everything that AM does can be viewed as testing the underlying body
04000 of heuristic rules. Gradually, this knowledge becomes better
04100 organized, its implications clearer. The resultant body of detailed
04200 heuristics may be the germ of a more efficient programme for
04300 educating math students than the current dogma$$ Currently, an
04400 educator takes the very best work any mathematician has ever done,
04500 polishes it until its brilliance is blinding, then presents it to the
04600 student to induce upon. Many individuals (e.g., Knuth and Polya) have
04700 pointed out this blunder. A few (e.g., Papert at MIT, Adams at
04800 Stanford) are experimenting with more realistic strategies for
04900 "teaching" creativity. See the references by these authors in the bibliography. $.
05000
05100 Another benefit of actually constructing AM is that of
05200 ⊗4experimentation⊗*: one can vary the concepts AM starts with, vary
05300 the heuristics available, etc., and study the effects on AM's
05400 behavior. Several such experiments were performed. One involved
05500 adding a couple dozen new concepts from an entirely new domain: plane
05600 geometry. AM busied itself exploring elementary geometric concepts,
05700 and was almost as productive there as in its original domain. New
05800 concepts were defined, and new conjectures formulated. Other
05900 experiments indicated that AM was more robust than anticipated; it
06000 withstood many kinds of "de-tuning". Others demonstrated the
06100 tremendous impact that a few key concepts (e.g., Equality) had on
06200 AM's behavior. Several more experiments and extensions have been
06300 planned for the future.
06400
00010 .if wantmotiv then start;
00100 . SSSEC(Motivation [optional])
00200
00300 .QQ
00400
00500 We need a super-mathematics in which the operations are as unknown as
00600 the quantities they operate on, and a super-mathematician, who does
00700 not know what he is doing when he performs these operations.
00800
00900 -- Eddington
01000
01100 .ESS
01200
01300
01400 Although the motivation for carrying out this research of course
01500 preceded the effort, I have delayed until this section a discussion
01600 of why this is worthwhile, why it was attempted.
01700
01800 First there was the inherent interest of getting a handle on
01900 scientific creativity. AM is partly a demonstration that some
02000 aspects of creative theory formation can be demystified, can be
02100 modelled as simple rule-governed behavior.
02200
02300 Related to this is the potential for learning from AM more about the
02400 processes of concept formation. This was touched on previously, and
02500 several experiments already performed on AM will be detailed later.
02600
02700 Third, AM itself may grow into something of pragmatic value. Perhaps
02800 it will become a useful tool for mathematicians, for educators, or as
02900 a model for similar systems in more "practical" fields. Perhaps in the
03000 future we scientists will be able to rely on automated assistants to
03100 carry out the "hack" phases of research, the tiresome legwork
03200 necessary for "secondary" creativity.
03300
03400 Historically, the domain of AM came from a search for a scientific
03500 field whose activities had no specific goal, and in which natural
03600 language abilities were unnecessary. This was to test out the BEINGs
03700 [Lenat 75b]
03800 ideas for a modular representation of knowledge.
03900
04000 It would be unfair not to mention the usual bad reasons for this
04100 research: the "Look ma, no hands" syndrome, the AI researcher's
04200 classic maternal urges, ego, the usual thesis drives, etc.
04300
04400 .end;
04500
00100 . SSSEC(Conclusions)
00200
00300 AM is forced to judge ⊗4a priori⊗* the value of each new concept, to
00400 lose interest quickly in concepts which aren't going to develop into
00500 anything. Often, such judgments can only be based on hindsight. For
00600 similar reasons, AM has difficulty formulating new heuristics which
00700 are relevant to the new concepts it creates. Heuristics are often
00800 merely compiled hindsight. While AM's "approach" to empirical
00900 research may be used in other scientific domains, the main limitation
01000 (reliance on hindsight) will probably recur. This prevents AM from
01100 progressing indefinitely far on its own.
01200
01300 This ultimate limitation was reached. AM's performance degraded more
01400 and more as it progressed further away from its initial base of
01500 concepts. Nevertheless, AM demonstrated that selected aspects of
01600 creative discovery in elementary mathematics could be adequately
01700 represented as a heuristic search process. Actually constructing a
01800 computer model of this activity has provided an experimental vehicle
01900 for studying the dynamics of plausible empirical inference.
02000
00100 .SSEC(Ways of viewing AM as some common process)
00200
00300 This section will provide a few metaphors: some hints for squeezing
00400 AM into paradigms with which the reader might be familiar. For
00500 example, the existence of heuristics in AM is functionally the same
00600 as the presence of domain-specific information in any knowledge-based
00700 system.
00800
00900 Consider assumptions, axioms, definitions, and theorems to be
01000 syntactic rules for the language that we call Mathematics. Thus
01100 theorem-proving, and the whole of textbook mathematics, is a purely
01200 syntactic process. Then the heuristic rules used by a mathematician
01300 (and by AM) would correspond to the semantic knowledge associated
01400 with these more formal methods.
01500
01600 Just as one can upgrade natural-language-understanding by
01700 incorporating semantic knowledge, so AM is only as successful as the
01800 heuristics it knows.
01900
02000 Four more ways of "viewing" AM as something else will be provided:
02100 (i) AM as a hill-climber, (ii) AM as a heuristic search program,
02200 (iii) AM as a mathematician, and (iv) AM as half a book.
02300
00100 . SSSEC(AM as Hill-climbing)
00200
00300 Let's draw an analogy between
00400 the process of
00500 developing new mathematics and the familiar
00600 process of hill-climbing. We may visualize AM as exploring a space
00700 using a measuring or "evaluation" function which imparts to it a topography.
00800
00900 Consider AM's core of very simple knowledge. By compounding its
01000 known concepts and methods, AM can explore beyond the frontier of
01100 this foundation a little
01200 wherever it wishes. The incredible variety of alternatives to
01300 investigate includes all known mathematics, much trivia, countless
01400 deadends, and so on. The only "successful" paths near the core are
01500 the narrow ridges of known mathematics (plus perhaps a few
01600 as-yet-undiscovered isolated peaks).
01700
01800 How can AM walk through this immense space, with any hope of
01900 following the few, slender trails of already-established
02000 mathematics (or some equally successful new fields)? AM must do
02100 hill-climbing: As new concepts are formed, decide how promising they
02200 are, and always explore the currently most-promising new concept. The
02300 evaluation function is quite nontrivial, and this thesis may be
02400 viewed as an attempt to study and explain and duplicate the
02500 judgmental criteria people employ. Preliminary attempts$$
02600 These took the form of informal simulations. Although far from controlled
02700 experiments, they indicated the feasability of attempting to create AM,
02800 by yielding an approximate figure for the amount of informal knowledge
02900 such a system would need.
03000 $ at codifying such
03100 "mysterious" emotive forces as intuition, aesthetics, utility,
03200 richness, interestingness, relevance... indicated that a large but
03300 not unmanageable collection of heuristic rules should suffice.
03400
03500 The important visualization to make is that with proper evaluation
03600 criteria, AM's planar mass of interrelated concepts is transformed
03700 into a three-dimensional relief map: the known lines of development
03800 become mountain ranges, soaring above the vast flat plains of trivia
03900 and inconsistency below.
04000
04100 Occasionally an isolated hill is discovered near the core;$$ E.g.,
04200 Conway's numbers, as described in [Knuth 74]. $
04300 certainly whole ranges lie undiscovered for long periods of time$$
04400 E.g., non-Euclidean geometries weren't thought of until 1848. $, and
04500 the terrrain far from the initial core is not yet explored at all.
04600
00100 . SSSEC(AM as Heuristic Search)
00200
00300 We earlier referred to AM as a
00400 kind of "heuristic search" program. That must mean that AM is
00500 exploring a particular "space," using some informal evaluation
00600 criteria to guide it.
00700
00800 The flavor of search which is used here is that of progressively
00900 enlarging a tree. Certain "evaluation-function" heuristics are used
01000 to decide which node of the tree to expand next, and other guiding
01100 rules are then used to produce from that node a few interesting
01200 successor nodes. To do mathematical research well, I claim that it is
01300 necessary and sufficent to have good methods for proposing new
01400 concepts from existing ones, and for deciding how interesting each
01500 "node" (partially-studied concept) is.
01600
01700 AM is initially supplied with a few facts about some simple math
01800 concepts. AM then explores mathematics by selectively enlarging that
01900 basis. One could say that AM consists of an active body of
02000 mathematical concepts, plus enough "wisdom" to use and develop them
02100 effectively. For "wisdom", read "heuristics". Loosely speaking, then,
02200 AM is a heuristic search program. To see this more clearly, we must
02300 explain what the nodes of AM's search space are, what the successor
02400 operators or links are, and what the evaluation function is.
02500
02600 AM's space can be considered to consist of all nodes which are
02700 consistent, partially-filled-in concepts. Then a primitive "legal
02800 move" for AM would be to (i) enlarge some facet of some concept, or
02900 (ii) create a new, partially-complete concept. Consider momentarily
03000 the size of this space. If there were no constraint on what the new
03100 concepts can be, and no informal knowledge for quickly finding
03200 entries for a desired facet, a blind "legal-move" program would go
03300 nowhere -- slowly! One shouldn't even call the activity such a
03400 program would be doing "math research."
03500
03600 The heuristic rules are used as little "plausible move generators".
03700 They suggest which facet of which concept to enlarge next, and they
03800 suggest specific new concepts to create. The only activities which AM
03900 will consider doing are those which have been motivated for some
04000 specific good$$ Of course, AM thinks a reason is "good" if -- and
04100 only if -- it was told that by a heuristic rule; so those rules had
04200 better be plausible, preferably the ones actually used by the
04300 experts. $ reason. A global ⊗4agenda of tasks⊗* is maintained,
04400 listing all the activities suggested but not yet worked on.
04500
04600 AM has a definite algorithm for rating the nodes of its space. Many
04700 heuristics exist merely to estimate the worth of any given concept.
04800 Other heuristics use these worth ratings to order the tasks on the
04900 global agenda list. Yet AM has no specific goal criteria: it can
05000 never "halt", never succeed or fail in any absolute sense. AM goes on
05100 forever$$ Technically, forever is about 100,000 list cells and a
05200 couple cpu hours. $.
05300
05400 Consider Nilsson's descriptions of depth-first searching and
05500 breadth-first searching
05600 ([Nilsson 71]).
05700 He has us maintain a list of "open" nodes.
05800 Repeatedly, he plucks the top one and expands it. In the process,
05900 some new nodes may be added to the Open list. In the case of
06000 depth-first searching, they are added at the top; the next node to
06100 expand is the one most recently created; the Open-list is being used
06200 as a push-down stack. For breadth-first search, new nodes are added
06300 at the bottom; they aren't expanded until all the older nodes have
06400 been; the Open-list is used as a queue. For heuristic search, or
06500 "best-first" search, new nodes are evaluated in some numeric way, and
06600 then "merged" into the already-sorted list of Open nodes.
06700
06800 .ONCE TURN ON "{⎇"
06900
07000 This process is very similar to the agenda mechanism AM uses to
07100 manage its search. This will be discussed in detail in Chapter
07200 {[2]AGENDA⎇. Each entry on the agenda consists of three parts:
07300 (i) a plausible task for AM
07400 to do, (ii) a list of reasons supporting that task, and (iii) a
07500 numeric estimate of the overall priority this task should have.
07600 When a task is suggested for some reason, it is added to the agenda.
07700 A task may be suggested several times, for different reasons. The
07800 global priority value assigned to each task is based on the combined
07900 value of its reasons. The control structure of AM is simply to
08000 select the task with the highest priority, execute it, and select a
08100 new one. The agenda mechanism appears to be a very well-suited data
08200 structure for managing a "best-first" search process.
08300
08400 Similar control structures were used in LT
08500 [Newell, Shaw, & Simon 57], the predictor part of
08600 Dendral
08700 [Buchanan et al 69], SIMULA-67 [Dahl 68],
08800 and KRL [Bobrow & Winograd
08900 77].
09000 The main difference is that in AM, symbolic reasons are
09100 used (albeit in trivial token-like ways) to decide whether -- and how
09200 much -- to boost the priority of a task when it is suggested again.
09300
09400 There are several difficulties and anomalies in forcing AM into the
09500 heuristic search paradigm.
09600 In a typical heuristic search
09700 (e.g., Dendral [Feigenbaum et al 71], Meta-Dendral [Buchanan et al 72],
09800 most game-playing programs [Samuel 67]),
09900 a "search space" is defined implicitly by a
10000 "legal move generator". Heuristics are present to constrain that
10100 generator so that only plausible nodes are produced.
10200 The second kind of heuristic
10300 search, of which AM is an example, contains no "legal move generator".
10400 Instead,
10500 AM's heuristics are used as plausible
10600 move generators.
10700 Those heuristics themselves implicitly define the possible tasks AM might
10800 consider, and ⊗4all⊗* such tasks should be plausible one. In the first kind of
10900 search, removing a heuristic widens the search space; in AM's kind of
11000 search, removing a heuristic ⊗4reduces⊗* it.
11100
11200 .HSEARCH: PAGE;
11300
11400 Another anomaly is that the operators which AM uses to enlarge and
11500 explore the space of concepts are themselves mathematical concepts
11600 (e.g., some heuristic rules result in the creation of new heuristic
11700 rules; "Compose" is both a concept and an operation which results in
11800 new concepts). Thus AM should be viewed as a mass of knowledge which
11900 enlarges ⊗4itself⊗* repeatedly. Typically,
12000 computer programs keep the information they "discover" quite
12100 separate from the knowledge they use to make discoveries$$ Of course
12200 this is often because the two kinds of knowledge are very
12300 different: For a chess-player, the first kind is "good board
12400 positions," and the second is "strategies for making a good move."
12500 Theorem-provers are an exception. They produce
12600 a new theorem, and then use it (almost like a new operator) in future proofs.
12700 A program to learn
12800 to play checkers [Samuel 67] has this same flavor, thereby indicating that
12900 this `self-help' property is not a function of the task
13000 domain, not simply a characteristic of mathematics. $
13100
13200 Perhaps the greatest difference between AM and typical heuristic
13300 search procedures is that AM has no well-defined target concepts or
13400 target relationships. Rather, its "goal criterion" -- its sole aim
13500 -- is to maximize the interestingness level of the activities it
13600 performs, the priority ratings of the top tasks on the agenda. It
13700 doesn't matter precisely which definitions or conjectures AM
13800 discovers -- or misses -- so long as it spends its time on plausible
13900 tasks. There is no fixed set of theorems that AM should discover, so
14000 AM is not a typical ⊗4problem-solver⊗*. There is no fixed set of
14100 traps AM should avoid,
14200 no small set of legal moves,
14300 and no winning/losing behavior,
14400 so AM is not a
14500 typical ⊗4game-player⊗*.
14600
14700 For example, no stigma is attached to the fact that AM never
14800 discovered real numbers$$ There are many "nice" things which AM
14900 didn't -- and can't -- do: e.g., devising ↓_geometric_↓ concepts from
15000 its initial simple set-theoretic knowledge. See the discussion of
15100 the limitations of AM, Section {[2]DIFSECNUM⎇.{[2]DIFSSECNUM⎇. $; it
15200 was rather surprising that AM managed to discover ⊗4natural⊗*
15300 numbers! Even if it hadn't done that, it would have been
15400 acceptable$$ Acceptable to whom? Is there really a domain-invariant
15500 criterion for judging the quality of AM's actions? See the
15600 discussions in Section {[2]EVALU⎇.1. $ if AM had simply gone off and
15700 developed ideas in set theory.
15800
00100 . SSSEC(AM as a Mathematician)
00200
00300 .AMAM: PAGE;
00400
00500 .AMAMSSEC: SSECNUM;
00600
00700 Before diving into the innards of AM, let's take a moment to discuss
00800 the totality of the mathematics which AM carried out. Like a
00900 contemporary historian summarizing the work of the Babylonian
01000 mathematicians, we shan't hesitate to use current terms and criticize
01100 by current standards.
01200
01300 AM began its investigations with scanty knowledge of a few
01400 set-theoretic concepts (sets, equality of sets, set operations).
01500 Most of the obvious set-theory relations (e.g., de Morgan's laws)
01600 were eventually uncovered; since AM never fully understood abstract
01700 algebra, the statement and verification of each of these was quite
01800 obscure. AM never derived a formal notion of infinity, but it
01900 naively established conjectures like "a set can never be a member of
02000 itself", and procedures for making chains of new sets ("insert a set
02100 into itself"). No sophisticated set theory (e.g., diagonalization)
02200 was ever done.
02300
02400 After this initial period of exploration, AM decided that "equality"
02500 was worth generalizing, and thereby discovered the relation
02600 "same-size-as". "Natural numbers" were based on this, and soon most
02700 simple arithmetic operations were defined.
02800
02900 Since addition arose as an analog to union, and multiplication as a
03000 repeated substitution followed by a generalized kind of unioning$$
03100 Take two bags A and B. Replace each element of A by the bag B. Remove
03200 one level of parentheses by taking the union of all elements of the
03300 transfigured bag A. Then that new bag will have as many elements as
03400 the product of the lengths of the two original bags. $ it came as
03500 quite a surprise when AM noticed that they were related (namely,
03600 N+N=2⊗7x⊗*N). AM later re-discovered multiplication in three other ways:
03700 as repeated addition, as the numeric analog of the Cartesian product
03800 of sets, and by studying the cardinality of power sets$$ The size of
03900 the set of all subsets of S is 2↑|↑S↑|. Thus the power set of A∪B has
04000 length equal to the ↓_product_↓ of the lengths of the power sets of A
04100 and B individually (assuming A and B are disjoint). $. These
04200 operations were defined in different ways, so it was an unexpected
04300 (to AM) discovery when they all turned out to be equivalent. These
04400 surprises caused AM to give the concept `Times' quite a high Worth
04500 rating.
04600
04700 Exponentiation was defined as repeated multiplication. Unfortunately,
04800 AM never found any obvious properties of exponentiation, hence lost
04900 all interest in it.
05000
05100 Soon after defining multiplication, AM investigated the process of
05200 multiplying a number by itself: squaring. The inverse of this turned
05300 out to be interesting, and led to the definition of square-root. AM
05400 remained content to play around with the concept of
05500 ⊗4integer⊗*-square-root. Although it isolated the set of numbers
05600 which had no square root, AM was never close to discovering
05700 rationals, let alone irrationals.
05800
05900 Raising to fourth-powers, and fourth-rooting, were discovered at this
06000 time. Perfect squares and perfect fourth-powers were isolated. Many
06100 other numeric operations and kinds of numbers were isolated: Odds,
06200 Evens, Doubling, Halving, etc. Primitive notions of numeric
06300 inequality were defined but AM never even discovered Trichotomy.
06400
06500 .ONCE TURN ON "{⎇"
06600
06700 The associativity and commutativity of multiplication indicated that
06800 it could accept a BAG of numbers as its argument. When AM defined
06900 the inverse operation corresponding to Times, this property allowed
07000 the definition to be: "any ⊗4bag⊗* of numbers (>1) whose product is
07100 x". This was just the notion of factoring a number x.
07200 Minimally-factorable numbers turned out to be what we call primes.
07300 Maximally-factorable numbers were also thought to be interesting.
07400
07500 Prime pairs were discovered in a bizarre way: by restricting addition
07600 (its arguments and its values) to Primes.$$ That is, consider the set
07700 of triples p,q,r, all primes, for which p+q=r. Then one of them must
07800 be "2", and the other two must therefore form a prime pair. $ AM
07900 conjectured the fundamental theorem of arithmetic (unique
08000 factorization into primes) and Goldbach's conjecture (every even
08100 number >2 is the sum of two primes) in a surprisingly symmetric way.
08200 The unary representation of numbers gave way to a representation as a
08300 bag of primes (based on unique factorization), but AM never thought
08400 of exponential notation.
08500 $$ A tangential note:
08600 All of the discoveries mentioned above were made by AM working
08700 by itself, with a human being observing its behavior. If the
08800 level of sophistication of AM's concepts were higher (or the level
08900 of sophistication of its users were lower), then it might be worthwhile
09000 to develop a nice user--system interface. The user in that case
09100 could -- and ought to -- work right along with AM as a co-researcher. $
09200 Since the key concepts of remainder,
09300 greater-than, gcd, and exponentiation were never mastered, progress
09400 in number theory was arrested.
09500
09600 When a new base of ⊗4geometric⊗* concepts was added, AM began finding
09700 some more general associations. In place of the strict definitions
09800 for the equality of lines, angles, and triangles, came new
09900 definitions of concepts we refer to as Parallel, Equal-measure,
10000 Similar, Congruent, Translation, Rotation, plus many which have no
10100 common name (e.g. the relationship of two triangles sharing a common
10200 angle). A cute geometric interpretation of Goldbach's conjecture was
10300 found$$ Given all angles of a prime number of degrees,
10400 (0,1,2,3,5,7,11,...,179 degrees), then any angle between 0 and 180
10500 degrees can be approximated (to within 1 degree) as the sum of two of
10600 those angles. $. Lacking a geometry "model" (an analogic
10700 representation like the one Gelernter employed), AM was doomed to
10800 failure with respect to proposing only plausible geometric
10900 conjectures.
11000
11100 Similar restrictions due to poor "visualization" abilities would crop
11200 up in topology. The concepts of continuity, infinity, and measure
11300 would have to be fed to AM before it could enter the domains of
11400 analysis. More and more drastic changes in its initial base would be
11500 required, as the desired domain gets further and further from simple
11600 finite set theory and elementary number theory.
11700
00100 . SKIP TO COLUMN 1; SSSEC(AM as a Thesis [optional])
00200
00300 .QQ
00400
00500 Walking home along a deserted street late at night, the reader may
00600 imagine himself to feel in the small of his back a cold, hard object;
00700 and to hear the words spoken behind him, `Easy now. This is a
00800 stick-up. Hand over your money.' What does the reader do? He
00900 attempts to generate the utterance. He says to himself, now if I were
01000 standing behind someone holding a cold, hard object against his
01100 back, what would make me say that? What would I mean by it? The
01200 reader is advised that he can only arrive at the deep structure of
01300 this book, and through the deep structure the semantics, if he
01400 attempts to generate the book for himself. The author wishes him
01500 luck.
01600
01700 -- Linderholm
01800
01900 .ESS
02000
02100 . TURN ON "{⎇";
02200
02300 Don't be scared by the weight of the document you're now holding.
02400 If you flip to page {[3]ENDTEXT⎇, you'll see that the last two-thirds
02500 are just appendices.
02600
02700 Each chapter is of roughly equal importance, which explains the huge variation
02800 in length.
02900 Start looking over Chapter {[2]EXAM1⎇ right away: it contains
03000 a detailed example of what AM does.
03100 Since you're reading this sentence now, we'll assume that
03200 you want a preview of
03300 what's to come in the rest of this document.
03400
03500 Chapter 3 covers the top-level control structure of the system, which is
03600 based around the notion of an `agenda' of tasks to perform.
03700 In Chapter 4 the low-level control structure is revealed: AM is really
03800 guided by a mass of heuristic rules of varying generality.
03900 Chapter 5 contains more than you want to know about the representation
04000 of knowledge in AM.
04100 The diagram showing some of AM's starting concepts
04200 (page {[3]TREECON⎇) is worth a look, even out of context.
04300
04400 Most of the results of the project are presented in Chapter 6. In addition to
04500 simply `running' AM, several experiments have been conducted with it.
04600 It's awkward to evaluate AM, and therefore Chapter 7 is quite long and detailed.
04700
04800 The appendices provide material which supplements the text.
04900 Appendix {[2]ALLCON⎇ contains a description of all the initial concepts,
05000 some examples of how they were coded into Lisp, and a partial list of the
05100 concepts AM defined and investigated along the way.
05200 Appendix {[2]ALLHEU⎇ exhibits all {[3]TRULES⎇ heuristics that AM is
05300 explicitly provided with.
05400 Appendix {[2]MAXDIV⎇ is essentially a math article, about the major discovery
05500 that AM motivated: maximally-divisible numbers. Finally,
05600 Appendix {[2]TRACES⎇ contains traces of AM in action: a long prose
05700 description, a long task-by-task description, and a long undoctored transcript
05800 excerpt. Appendix {[2]GLOS⎇ hasn't been mentioned yet, and forms the
05900 subject of the remainder of this section.
06000
06100 This thesis -- and its readers -- must come to grips with a very
06200 interdisciplinary problem. For the reader whose background is in
06300 Artificial Intelligence, most of the system's actions -- the
06400 "mathematics" it does -- may seem inherently uninteresting. For the
06500 mathematician, the word "LISP" signifies nothing beyond a speech
06600 impediment (to Artificial Intelligence types it also connotes a
06700 programming impediment). If I don't describe "LISP" the first time I
06800 mention it, a large fraction of potential readers will never realize
06900 that potential. If I ⊗4do⊗* stop to describe LISP, the other readers
07000 will be bored.
07100
07200
07300 In an attempt not to lose readers due to jargon, two glossaries of
07400 terms have been compiled. Appendix {[2]GLOS⎇.1 (p. {[3]GLOS1P⎇)
07500 contains capsule descriptions of the mathematical terms, ideas, and
07600 notations used in this thesis. Appendix {[2]GLOS⎇.2 renders the
07700 analogous service for Artificial Intelligence jargon and computer
07800 science concepts.
07900